package com.ry.day1129;
import java.util.*;

public class LC40 {

    static class MyQueue {
        Stack<Integer> s1 = null;
        Stack<Integer> s2 = null;
        public MyQueue() {
            // do intialization if necessary
            s1 = new Stack<>();
            s2 = new Stack<>();
        }

        /*
         * @param element: An integer
         * @return: nothing
         */
        public void push(int element) {
            // write your code here
            s1.push(element);
        }

        /*
         * @return: An integer
         */
        public int pop() {
            // write your code here
            int res;
            if(!s2.isEmpty()){
                res= s2.pop();
            }else{
                while (!s1.isEmpty()){
                    s2.push(s1.pop());
                }

                res= s2.pop();
            }
            return res;
        }

        /*
         * @return: An integer
         */
        public int top() {
            int res;
            if(!s2.isEmpty()){
                res = s2.peek();
            }else{
                while (!s1.isEmpty()){
                    s2.push(s1.pop());
                }
                res = s2.peek();
            }
            return res;
        }
    }


    static class MyQueue01 {
        Stack<Integer> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();
        public MyQueue01() {
            // do intialization if necessary
        }

        /*
         * @param element: An integer
         * @return: nothing
         */
        public void push(int element) {
            // write your code here
            s1.push(element);
        }

        /*
         * @return: An integer
         */
        public int pop() {
            // write your code here
            int data;
            if(!s2.isEmpty()){
                data = s2.peek();
                s2.pop();
            }else{
                while (!s1.isEmpty()){
                    int t = s1.peek();
                    s1.pop();
                    s2.push(t);
                }
                data= s2.peek();
                s2.pop();
            }

            return data;
        }

        /*
         * @return: An integer
         */
        public int top() {
            // write your code here
            int data;
            if(!s2.isEmpty()){
                data = s2.peek();
            }else{
                while (!s1.isEmpty()){
                    int t = s1.peek();
                    s1.pop();
                    s2.push(t);
                }
                data= s2.peek();
            }

            return data;
        }

    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
40 · 用栈实现队列
算法
中等
通过率
55%

题目
题解44
笔记
讨论99+
排名
记录
描述
正如标题所述，你只能使用两个栈来实现队列的一些操作。队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。pop和top方法都应该返回第一个元素的值。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


假设调用pop()函数的时候，队列非空

样例
样例 1：

输入：

队列操作 =
    push(1)
    pop()
    push(2)
    push(3)
    top()
    pop()
输出：

1
2
2
解释：

pop和top方法都应该返回第一个元素的值。

样例 2：

输入：

队列操作 =
    push(1)
    push(2)
    push(2)
    push(3)
    push(4)
    push(5)
    push(6)
    push(7)
    push(1)
输出：

[]
解释：

没有输出。

挑战
仅使用两个栈来实现它，不使用任何其他数据结构，push，pop 和 top的复杂度都应该是均摊O(1)的

相关知识
学习《九章算法班随课教程》课程中的7.8如何用两个栈实现队列相关内容 ，了解更多相关知识！
标签
相关题目

955
用循环数组来实现队列
中等

12
带最小值操作的栈
中等

492
队列维护
简单

493
维护队列 II
简单

546
按接口实现队列
简单
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
1849/1887
已开启智能提示
发起考试
30 分 00 秒


 */
